The process of rendering two-dimensional images from three-dimensional scenes is commonly referred to as image processing. As the modern computer industry evolves image processing evolves as well. One particular goal in the evolution of image processing is to make two-dimensional simulations or renditions of three-dimensional scenes as realistic as possible. One limitation of rendering realistic images is that modern monitors display images through the use of pixels.
A pixel is the smallest area of space which can be illuminated on a monitor. Most modern computer monitors will use a combination of hundreds of thousands or millions of pixels to compose the entire display or rendered scene. The individual pixels are arranged in a grid pattern and collectively cover the entire viewing area of the monitor. Each individual pixel may be illuminated to render a final picture for viewing.
One technique for rendering a real world three-dimensional scene onto a two-dimensional monitor using pixels is called rasterization. Rasterization is the process of taking a two-dimensional image represented in vector format (mathematical representations of geometric objects within a scene) and converting the image into individual pixels for display on the monitor. Rasterization is effective at rendering graphics quickly and using relatively low amounts of computational power; however, rasterization suffers from several drawbacks. For example, rasterization often suffers from a lack of realism because it is not based on the physical properties of light, rather rasterization is based on the shape of three-dimensional geometric objects in a scene projected onto a two dimensional plane. Furthermore, the computational power required to render a scene with rasterization scales directly with an increase in the complexity of the scene to be rendered. As image processing becomes more realistic, rendered scenes also become more complex. Therefore, rasterization suffers as image processing evolves, because rasterization scales directly with complexity.
Several alternative techniques rendering a real world three-dimensional scene onto a two-dimensional monitor using pixels have been developed based upon more realistic physical modeling. One such physical rendering technique is called ray tracing. The ray tracing technique traces the propagation of imaginary rays, rays which behave similar to rays of light, into a three-dimensional scene which is to be rendered onto a computer screen. The rays originate from the eye(s) of a viewer sitting behind the computer screen and traverse through pixels, which make up the computer screen, towards the three-dimensional scene. Each traced ray proceeds into the scene and may intersect with objects within the scene. If a ray intersects an object within the scene, properties of the object and several other contributing factors are used to calculate the amount of color and light, or lack thereof, the ray is exposed to. These calculations are then used to determine the final color of the pixel through which the traced ray passed.
The process of tracing rays is carried out many times for a single scene. For example, a single ray may be traced for each pixel in the display. Once a sufficient number of rays have been traced to determine the color of all of the pixels which make up the two-dimensional display of the computer screen, the two dimensional synthesis of the three-dimensional scene can be displayed on the computer screen to the viewer.
Ray tracing typically renders real world three-dimensional scenes with more realism than rasterization. This is partially due to the fact that ray tracing simulates how light travels and behaves in a real world environment, rather than simply projecting a three-dimensional shape onto a two dimensional plane as is done with rasterization. Therefore, graphics rendered using ray tracing more accurately depict on a monitor what our eyes are accustomed to seeing in the real world.
Furthermore, ray tracing also handles increases in scene complexity better than rasterization as scenes become more complex. Ray tracing scales logarithmically with scene complexity. This is due to the fact that the same number of rays may be cast into a scene, even if the scene becomes more complex. Therefore, ray tracing does not suffer in terms of computational power requirements as scenes become more complex as rasterization does.
One major drawback of ray tracing, however, is the large number of calculations, and thus processing power, required to render scenes. This leads to problems when fast rendering is needed. For example, when an image processing system is to render graphics for animation purposes such as in a game console. Due to the increased computational requirements for ray tracing it is difficult to render animation quickly enough to seem realistic (realistic animation is approximately twenty to twenty-four frames per second).
With continued improvements in semiconductor technology in terms of clock speed and increased use of parallelism; however, real time rendering of scenes using physical rendering techniques such as ray tracing becomes a more practical alternative to rasterization. At the chip level, multiple processor cores are often disposed on the same chip, functioning in much the same manner as separate processor chips, or to some extent, as completely separate computers. In addition, even within cores, parallelism is employed through the use of multiple execution units that are specialized to handle certain types of operations. Hardware-based pipelining is also employed in many instances so that certain operations that may take multiple clock cycles to perform are broken up into stages, enabling other operations to be started prior to completion of earlier operations. Multithreading is also employed to enable multiple instruction streams to be processed in parallel, enabling more overall work to performed in any given clock cycle.
Despite these advances, however, the adoption of physical rendering techniques faces a number of challenges. One such challenge relates to the generation of the data structures that are utilized by such physical rendering techniques.
In general, rendering processes often can be logically broken into frontend and backend processes. The frontend process is used to basically build primitives for a scene to be depicted in the displayed image. A primitive is the basic geometry element used to represent an object in a scene, and in many conventional techniques, primitives are defined as triangles. Objects to be placed in a scene may be predefined and loaded during the frontend process, or objects can be built on-the-fly based upon mathematical algorithms that define the shape of a 3D object.
The frontend process typically places objects in a scene, determines and/or creates the primitives for those objects, and assigns colors or textures to each of the primitives. Once objects and primitives are placed, no movement of those objects or primitives is typically permitted.
The backend process takes the primitives and the colors or textures assigned to those primitives by the frontend process, and draws the 2D image, determining which primitives are visible from the desired viewpoint, and based upon the displayed primitives, assigning appropriate colors to all of the pixels in the image. The output of the backend process is fed to an image buffer for display on a video display.
For a physical rendering backend, the output of the frontend process, the list of primitives and their assigned colors or textures, often must be transformed into a data structure that can be used by the physical rendering backend. In many physical rendering techniques, such as ray tracing and photon mapping, this data structure is referred to as an Accelerated Data Structure (ADS).
Given the relatively high processing requirements for physical rendering techniques, the ADS enables fast and efficient retrieval of primitives to assist in optimizing the performance of such techniques. An ADS may be implemented, for example, as a spatial index, which divides a three-dimensional scene or world into smaller volumes (smaller relative to the entire three-dimensional scene), within which geometric primitives are placed. Thus, for example, a ray tracing image processing system can use the known boundaries of these smaller volumes to determine if a ray may intersect primitives contained within the smaller volumes. If a ray does intersect a volume containing primitives, then a ray intersection test can be run using the trajectory of the ray against the known location and dimensions of the primitives contained within that volume. If a ray does not intersect a particular volume then there is no need to run any ray-primitive intersection tests against the primitives contained within that volume. Furthermore, if a ray intersects a bounding volume that does not contain primitives then there is no need to run any ray-primitive intersections tests against that bounding volume. Thus, by reducing the number of ray-primitive intersection tests that may be necessary, the use of a spatial index greatly increases the performance of a ray tracing image processing system.
An ADS may be implemented, for example, with a tree data structure, where nodes in the tree represent volumes within the three-dimensional scene, and with child nodes representing sub-volumes of the volumes represented by their respective parent nodes. Each primitive in a scene is typically placed in the lowest level node representing the volume within which such primitive is contained. By navigating from a root or world node for the tree, and then successively down through the tree based upon the current position of a ray, and the known boundaries of the volumes represented by the nodes in the tree, the primitive(s) with which the ray could potentially intersect can be readily and efficiently ascertained.
An ADS, however, can be computationally expensive to create, and can require a sizable memory allocation. Moreover, given that a new ADS is typically required for each frame, the processing overhead required to create the ADS can be substantial.
One step that can have a significant impact on the processing overhead associated with creating an ADS is the initialization of the ADS. Typically, the memory required for an ADS must be allocated to the ADS, either through a fixed allocation, which is limited in terms of flexibility since the size of an ADS can vary from frame to frame, or through dynamic allocation, so that memory is allocated as it is needed during the creation of the ADS. In order to ensure that allocated memory is not orphaned after an ADS is no longer being used, it may be necessary to deallocate the memory allocated to an ADS for a prior image frame before allocating new memory for the ADS for a new image frame. Allocating and deallocating memory, however, are often computationally expensive operations, which can adversely impact system performance, particularly when a new ADS is created for each image frame.
In the alternative, rather than deallocating the memory allocated to the ADS used for the prior image frame and allocating new memory for the ADS for the new image frame, the same allocated memory can be reused for each image frame. Doing so, however, would typically require all of the previous data for the ADS to be overwritten to in effect wipe out the prior ADS from the allocated memory. Given the size of the memory allocation for an ADS, particularly in complex scenes, the overhead associated with clearing out the allocated memory prior to creating a new ADS would also adversely impact system performance.
Therefore, a need exists in the art for minimizing the processing overhead associated with generating an ADS, and in particular, for minimizing the processing overhead associated with resetting or initializing the memory in which an ADS will be created.